Data is generally information of interest produced by an entity or a device. The source of data may be a device or a component within a device, such as a magnetic or optical storage device. In many practical applications, the data is communicated over a communication channel. The communication channel might be a wired or wireless connection to another device or to a component within the device which is the source of data for the communication channel. Communication channels add noise to data, which may corrupt the data and make portions of the data unrecognizable. Channel coding schemes seek to compensate for such problems by providing for verification of data and some ability to correct corrupted data. Many forms of channel coding have been developed and used.
A particularly powerful form of channel coding is known as turbo coding. The turbo encoder is a combination of two encoders which are individually weak, but are combined to produce a powerful coding scheme in a simple fashion. The input to a turbo encoder is a set of system data bits. Two encoders generate parity symbols from a simple code, typically a recursive convolutional code. One encoder creates the parity code directly from the system data bits. The other encoder produces the parity symbols from a permuted version of the system data bits obtained from an interleaver. Each of the separate encoders has a small number of states. The system data bits are sent over the communication channel with the separate parity symbols produced by the encoders. The permutation conducted by the interleaver ensures that in all but a small number of cases, when one encoder produces a low weight code word the other encoder will produce a high weight code word. Thus, the combination of the constituent codes is powerful.
At the decode side of a channel, there are two decoders. Each decoder trades estimates of the information bits and uses the estimate of the other and the data received from the channel to produce additional estimates using a decoding algorithm. Once satisfactory convergence is reached between the two decoders, the decoded channel output is available from the estimate of either of the decoders.
Partial response channels are typically used in magnetic data devices, such as disk drives. Partial Response Maximum Likelihood (PRML) is a technique to decode data in the presence of inter-symbol interference (ISI). ISI results from the overlap of analog signal peaks now streaming through disk drive read/write heads at higher and higher rates. PRML technology first converts the heads' analog signal to a digital signal, then uses the digital signal to detect data bits. Partial response is an equalization or filtering technique that controls intersymbol interference at multiples of a specified sampling interval. Maximum likelihood detection refers to the conversion of the partial response signal to data from additional decoding applied to the samples of the filtered signal. Viterbi detection implements a maximum likelihood detection algorithm that determines the data sequence for which the corresponding sampled partial response signal provides the best match of least error with the actual (noisy) samples of the channel output signal. The pattern that has the least error (difference) is the one with the maximum likelihood to be correct.
Various works have applied parallel concatenated turbo codes with iterative decoding to partial response channels of interest in digital recording. See, W. E. Ryan, Performance of High Rate Turbo Codes on a PR4 Equalized Magnetic Recording Channel, from Proceedings of IEEE Int'l Conference on Communications in Atlanta, Ga. (June 1998); W. E. Ryan et al., Combined turbo Coding and Turbo Equalization for PR-4 Equalized Lorentzian Channels, from Proceedings of the conference on Information Sciences and Systems (March 1998); C. Heegard, Turbo coding for Magnetic Recording, from Proceedings for Winter 1998 IEEE Information Theory Workshop in San Diego, Calif., pp. 18-19, (February 1998); W. Pusch et al., Turbo-Codes Matched to the 1-D2 Partial Response Channel, from proceedings of IEEE Intn'l Symposium on Information Theory in Cambridge, Mass. (August 1998). Others have investigated the performance of a serial concatenation of a high rate convolutional code, interleaver, and partial response channel, with iterative decoding. See, Souvignier et al., Turbo Codes for PR4: Parallel Versus Serial Concatenation, from Proceedings of IEEE Intn'l Conference on Communications in Vancouver, BC, Canada, June 1999; Öberg and Siegel, Performance Analysis of turbo Equalized Dicode Partial-Response Channel, in Proceedings of the 35th Annual Allerton Conference on Communications, Control, and Comp. in Monticello, Ill., pp. 230-39 (September 1998). The simple scheme performed as well as more complex turbo coding systems down to a bit error rate (BER) of about 10−5. Nonetheless, the convolutional coding itself is an impediment to further complexity reduction.
In addition, PRML and other data encoding schemes present problems to channel coding techniques. Data encoding schemes often have constraints which define conditions that the sequence of data may not violate. As a practical matter, PRML requires runlength constraints. Runlength constraints limit the number of consecutive bits that may be identical. Turbo coding schemes, which use an interleaver, make it difficult to have constraints in the channel because the interleaving of parity and data in pseudo-random fashion eliminates the possibility of imposing a constraint on the channel data stream.
In T. Conway, “A New Target Response with Parity Coding for High Density Magnetic Recording Channels,” IEEE Transactions on Magnetics, Vol. 34, no. 4, July 1998, pp. 2382-2386, it is shown that, at densities of 3 and 3.5 bits per PW50, a parity-check code will detect a single occurrence of either of the two dominant error events on a Lorentzian channel equalized to the partial-responses target h(D)=(1−D2) (2+2D+D2). An even-length code with odd parity is used to provide runlength constraints. Addition of a parity bit to a high-rate runlength constrained code is also proposed as a way to further reduce maximum runlengths of identical binary digits. The decoder consists of a Viterbi detector matched to the partial-response target, followed by a post-processor. The post-processor uses the outputs of the Viterbi detector to generate estimates of the noise, then correlates the noise estimates with the two dominant error events, at each bit time. When a parity violation is detected in a code word, the type and location of the most likely error event within the code word or straddling its boundaries is determined from the largest noise correlation value. This method incorporating a parity-check code, channel Viterbi detector, and postprocessor is shown to achieve performance comparable to that of previous higher-order PRML systems that incorporate distance-enhancing constrained codes. However, for future data storage systems, there remains the need for a coding and decoding method that provides even greater performance gains, while maintaining high rate, code runlength constraints, and reduced-complexity decoding.
Thus, improvements and variations have been made to the general turbo coding scheme since its introduction, seeking to enhance performance and reduce complexity. There nonetheless remains a need for an improved channel coding method with reduced implementation complexity that can achieve coding gains comparable or in excess to prior turbo coding techniques. It is an object of the invention to provide such an improved method. There further remains a need to provide an improved channel coding scheme which can ensure the meeting of runlength constraints in the channel. It is a further object of the invention to provide such an improved coding scheme.